package com.xy6.algo.dynamic;

/**
 * 最大子数组和问题
 * <pre>
 * 一个有N个整数元素的一维数组(A[0], A[1],...,A[n-1], A[n])，这个数组当然有很多子数组，那么数组之和的最大值是什么呢？
 * 要求写出时间复杂度为O(n)的最优解法
 * 例如有数组 int A[5] = {-1, 2, 3, -4, 2};
 * 符合条件的子数组为  2,3  即答案为 5;
 * 1.子数组必须是连续的。
 * 2.不需要返回子数组的具体位置。
 * 3.数组中包含：正整数，零，负整数。
 * 
 * </pre>
 * 
 * @author zhang
 * @since 2017-11-23
 */
public class MaxSubArray {

	/**
	 * 计算最大子数组和
	 * 
	 * @param a
	 * @return
	 */
	public static int calc(int[] a){
		int[] b = new int[a.length];
		b[0] = a[0];
		int max = a[0];
		for (int i = 1; i < a.length; i++) {
			if(a[i] > 0){
				b[i] = b[i - 1] + a[i]; 
			} else {
				b[i] = a[i];
			}
			b[i] = max(b[i], a[i]);
			max = max(max, b[i]);
		}
		
		return max;
	}
	
	/**
	 * 获取两个元素中的较大值
	 * 
	 * @param i
	 * @param j
	 * @return
	 */
	private static int max(int i, int j){
		return i > j ? i : j;
	}

}
